package leetcode.code2096;

import leetcode.IDebug;
import leetcode.helper.H;
import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

public class Solution implements IDebug {

	TreeNode proot;
	int startValue, destValue;
	int size;

	public String getDirections(TreeNode root, int startValue, int destValue) {
		proot = null;
		this.startValue = startValue;
		this.destValue = destValue;
		this.find(root);
		StringBuffer R1 = new StringBuffer();
		this.LR(proot.left, 'L', R1, 1);
		StringBuffer R2 = new StringBuffer();
		this.LR(proot.right, 'R', R2, 1);
		if (size > 0) {
			return R1.length() > 0 ? this.up(size, R1) : this.up(size, R2);
		}
		return R1.length() > 0 ? R1.reverse().toString() : R2.reverse().toString();
	}

	private String up(int size, StringBuffer sb) {
		for (int i = 0; i < size; i++) {
//			sb.insert(0, 'U');
			sb.append('U');
		}
		return sb.reverse().toString();
	}

	private boolean LR(TreeNode root, char from, StringBuffer sb, int cnt) {
		if (root == null) {
			return false;
		}
		if (root.val == destValue) {
			sb.insert(0, from);
			return true;
		}
		if (root.val == startValue) {
			size = cnt;
		}
		boolean L = this.LR(root.left, 'L', sb, cnt + 1);
		boolean R = this.LR(root.right, 'R', sb, cnt + 1);
		if (L || R) {
//			sb.insert(0, from);
			sb.append(from);
			return true;
		}
		return false;
	}

	private int find(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int ans = this.find(root.left) + this.find(root.right);
		if (root.val == startValue || root.val == destValue) {
			ans += 1;
		}
		if (ans == 2 && proot == null) {
			proot = root;
		}
		return ans;
	}

	@Override
	public void debug4() {
		this.getDirections(TreeArray.array2tree(
				H.str2array4("[2,10,4,8,9,3,11,null,null,7,null,null,null,null,null,1,null,null,5,6]")), 5, 4);
//		this.getDirections(TreeArray.array2tree(H.str2array4("[5,1,2,3,null,6,4]")),3, 6);
//		this.getDirections(TreeArray.array2tree(H.str2array4("[1,3,8,7,null,4,5,6,null,null,null,null,null,null,2]")),2, 1);

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
